package com.lwl.Algorithmic_data_structure.滑动窗口;

import com.lwl.Utils.PrintUtil;
import org.junit.Test;

import java.util.LinkedList;

/**
 * 给一个数组，返回求每w长的数组中的最大值
 */
public class SlidingWindowMaxArray {
    @Test
    public void test(){
        int[] maxWindow = getMaxWindow(new int[]{1, 2, 3, 1, 5, 4, 3, 3, 9}, 3);
        PrintUtil.printArray(maxWindow);
    }
    public static int[] getMaxWindow(int[] arr, int w) {
        if (arr == null || w < 1 || arr.length < w){
            return null;
        }
        int N = arr.length;
        int[] res = new int[N - w + 1];
        int index = 0;
        //存数组下标
        LinkedList<Integer> doubleList = new LinkedList<>();
        for (int R = 0; R < N; R++) {
            while (!doubleList.isEmpty() && arr[R] >= arr[doubleList.peekLast()]){
                doubleList.pollLast();
            }
            doubleList.addLast(R);
            //R - w 是滑动窗口的前一个数，如果当前最大值下表等于R-w，说明他已经过期了
             if (doubleList.peekFirst() == R - w){
                    doubleList.pollFirst();
             }
             if (R >= w - 1){
                 res[index++] = arr[doubleList.peekFirst()];
             }
        }
        return res;
    }
}
